package algorithm

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func reConstructBinaryTree(pre, in []int) *TreeNode {
	root := reConstructBinaryTreeDetail(pre, 0, len(pre)-1, in, 0, len(in)-1)
	return root
}
func reConstructBinaryTreeDetail(pre []int, pl, pr int, in []int, il, ir int) *TreeNode {
	if pl > pr || il > ir {
		return nil
	}
	treeNode := &TreeNode{Val: pre[pl]}
	for i := il; i < ir+1; i++ {
		if in[i] == pre[pl] {
			treeNode.Left = reConstructBinaryTreeDetail(pre, pl+1, pr+i-il, in, il, i-1)
			treeNode.Right = reConstructBinaryTreeDetail(pre, pl+i-il+1, pr, in, i+1, ir)
		}
	}
	return treeNode
}

func RunReConstructBinaryTree() {
	pre := []int{3, 9, 20, 15, 7}
	in := []int{9, 3, 15, 20, 7}
	root := reConstructBinaryTree(pre, in)
	fmt.Println(root.Val)
}

// 打印一个树
func (root *TreeNode) String() {
	if root == nil {
		return
	}

}

// 求个树身
func getDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + Max(getDepth(root.Left), getDepth(root.Right))
}
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
